package code1.linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * 原题链接：https://leetcode.cn/problems/linked-list-cycle-ii/
 */
public class P142 {

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
          val = x;
          next = null;
        }
    }

    //判断链表是否有环，如果有环就返回环的入口
    //快慢指针法(时间复杂度：O(n))
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;        //快指针每次走两步
            slow=slow.next;             //慢指针每次走一步
            //若有环中存在则快指针先进入环，且二者必在环中相遇
            if(fast==slow){
                ListNode index1=head;       //设从head到环入口的距离为x,环入口到相遇点的距离为y,相遇点到环入口的距离为z
                ListNode index2=fast;       //快指针走过的距离为：x+y+n*(y+z)、慢指针走过的距离为：x+y、且满足：x+y+n*(y+z)=2*(x+y)
                // 推导可得：x=(n-1)(y+z)+z，若两指针从head和相遇点处同步出发，则二者的相遇点即为环的入口
                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    //哈希表法(时间复杂度：O(n*n))
    public ListNode detectCycle2(ListNode head) {
        Set<ListNode> set=new HashSet<>();  //没什么好说的
        ListNode cur=head;
        while(cur!=null){
            if(!set.add(cur)){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

}
